package com.hsp.Demo_03_object;

public class Demo_08 {
    public static void main(String[] args) {
        /*
        迷宫
        有一个这样的迷宫：
1 1 1 1 1 1 1
1 0 1 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1  == 出口是这一排的最后这个0，只要走到这个位置，即代表走出了迷宫
1 1 1 1 1 1 1
        迷宫是 8 行 7列， 其中1 表示障碍物， 不能通过， 0表示通道，可以走的
            如何通过程序，来找到最近的通过的路
        */
        int[][] map = new int[8][7];
        MiGong miGong = new MiGong();
        miGong.miMethod(map);
        miGong.findWay(map, 1, 3);

        //5、打印该二维数组：
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[i].length; j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

class MiGong{

    public void miMethod(int[][] map){
        //1、先定义一个二维数组，来表示一个迷宫
        //map
        //2、该二维数组中，第一行和最后一行需要赋值为： 1
        for(int i = 0; i < map[0].length; i++){
            map[0][i] = 1;
            map[map.length-1][i] = 1;
        }

        //3、该数组的第一列和最后一列需要赋值为：1
        for(int i = 0; i < map.length; i++){
            map[i][0] = 1;
            map[i][map[0].length-1] = 1;
        }

        //4、第四排的第2 、 3列需要赋值为： 1
        map[3][1] = 1;
        map[3][2] = 1;

    }

    /*
    使用递归回溯的思想来解决老鼠出迷宫：
        1、findWay方法专门用来找出迷宫的路径
        2、如果找到，就返回true,否则返回false
        3、map就是二维数组，即表示迷宫
        4、i、j 就是老鼠当前的位置，初始化的位置为(1,1)
        5、因为我们是通过递归来找路，所以我们先规定，map数组的各个值的含义
            0：表示可以走 1：表示障碍物 2：表示可以走 3：表示走过，但是走不通的路
        6、当map[6][5] = 2, 就说明已经找到了通路，，就可以结束了，否则就继续找。
        7、确定老鼠找路的策略： 下->右->上->左
     */
    public boolean findWay(int[][] map, int i, int j){
        if(map[6][5] == 2){
            return true;
        }else{
            if(map[i][j] == 0){
                map[i][j] = 2;
                if(findWay(map, i+1, j)){
                    return true;
                }else if(findWay(map,i, j+1)){
                    return true;
                }else if(findWay(map, i-1, j)){
                    return true;
                }else if(findWay(map, i, j-1)){
                    return true;
                }else{
                    map[i][j] = 3;
                    return false;
                }
            }else{
                return false;
            }
        }

    }

}